public class Solution {
    public static int maxProfit(int[] prices) {
        int n = prices.length;
        int minIndex = 0,min = prices[0];
        int ret = Integer.MIN_VALUE;
        for(int i = 1;i < n;i++) {
            while(minIndex < i) {  //找第i天之前的最小值
                if(prices[minIndex] > prices[i]) min = prices[i];
                minIndex++;
            }
            ret = Math.max(prices[i] - min,ret);
        }
        return ret;
    }

    public static int findMin(int[] arr,int i) {  //找到[0,i]区间的最小值
        int min = arr[0];
        for(int j = 1;j <= i;j++) {
            if(arr[j] < min) min = arr[j];
        }
        return min;
    }
    //////////////////////////////////////////////////
    public static int maxProfit1(int[] prices) {
        // 两个维度描述状态：交易次数、第几天
        int n = prices.length;
        int[][] f = new int[3][n]; // 第i天结束持有股票
        int[][] g = new int[3][n]; // 第i天结束没有股票
        f[0][0] = -prices[0];
        f[1][0] = -0x3f3f3f3f;
        f[2][0] = -0x3f3f3f3f;
        g[1][0] = -0x3f3f3f3f;
        g[2][0] = -0x3f3f3f3f;
        for (int i = 0; i < 3; i++) {
            for (int j = 1; j < n; j++) {
                f[i][j] = Math.max(f[i][j - 1], g[i][j - 1] - prices[i]);
                g[i][j] = g[i][j - 1];
                if (i - 1 >= 0)
                    g[i][j] = Math.max(f[i - 1][j-1] + prices[i], g[i][j]);


            }
        }
        return Math.max(Math.max(g[0][n-1],g[1][n-1]),g[2][n-1]);
    }
    //////////////////////////////////////////////////
    public static int maxProfit(int k, int[] prices) {
        int n = prices.length;
        int[][] f = new int[k][n];
        int[][] g = new int[k][n];
        int INF = -0x3f3f3f3f;
        f[0][0] = -prices[0];
        f[1][0] = -prices[0];
        for(int i = 0;i < k;i++) {
            for(int j = 1;j < n;j++) {
                f[i][j] = Math.max(f[i][j-1],g[i][j-1] - prices[j]);
                g[i][j] = g[i][j-1];
                if(i - 1 >= 0) g[i][j] = Math.max(f[i-1][j-1] + prices[j],g[i][j-1]);
            }
        }
        int max = 0;
        for(int i = 0;i < k;i++) max = Math.max(max,g[i][n-1]);
        return max;
    }



    public static void main(String[] args) {
        int[] arr = {3,2,6,5,0,3};
        maxProfit(2,arr);
    }
}
